#include <iostream>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
private:
    bool is_valid(string& s) {
        int count = 0;
        for (char item : s) {
            if (item == '(') {
                count++;
            } else if (item == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        unordered_set<string> map;
        queue<string> queue;
        queue.push(s);
        bool end = false;
        while (true) {
            unordered_set<string> set;
            for (int i = 0, len = queue.size(); i < len; i++) {
                string s = queue.front();
                queue.pop();
                if (is_valid(s)) {
                    map.insert(s);
                    end = true;
                } else {
                    for (int i = 0; i < s.size(); i++) {
                        set.insert(s.substr(0, i) + s.substr(i + 1));
                    }
                }
            }
            if (end) {
                break;
            }
            for (string item : set) {
                queue.push(item);
            }
        }
        return vector<string>(map.begin(), map.end());
    }
};

int main() {
    Solution solution;
    vector<string> output = solution.removeInvalidParentheses("()())()");
    for (string item : output) {
        cout << item << endl;
    }
}